package algorithme;

import java.util.Arrays;

public class UnionFind {
	//liste des parents des sommets
	private int[] parents;
	//nombre de sommets du graphe
	private int N;
	
	//créé un objet UnionFind pour un graphe à n sommets
	public UnionFind(int n) {
		parents = new int[++n];
		Arrays.fill(parents, n);
		this.N = n;
	}

	public UnionFind(UnionFind u) {
		parents = new int[u.parents.length];
		for (int i = 0; i < u.parents.length; ++i)
			parents[i] = u.parents[i];
		this.N = u.N;
	}
	
	//renvoie le père du sommet c
	public int find(int c) {
		if (parents[c] >= N)
			return c;
		int f = find(parents[c]);
		parents[c] = f;
		return f;
	}
	
	//lie les sommets i et j
	public void link(int i, int j) {
		assert(find(i) != find(j));
		if (parents[i] < parents[j])
			parents[i] = j;
		else if (parents[i] > parents[j])
			parents[j] = i;
		else {
			parents[j] = i;
			++parents[i];
		}
	}
	
	//unifie les sommets i et j (ils sont alors considérés identiques)
	public void union(int i, int j) {
		int fi = find(i), fj = find(j);  
		if (fi != fj)
			link(fi, fj);
	}
}
